/**
 * Created by asus on 2017/9/26.
 */
public class MyLinkedList<T> {
    private int size=0;		   //列表中元素的个数
    private Node firstNode;    //列表中的头节点，此节点并不存储任何数据
    private Node lastNode;     //列表着的尾节点，此节点不存储任何数据

    public MyLinkedList(){
        //初始化头节点,此时头节点的前驱节点指向null,后继节点指向null
        //因为此时尾节点还没初始化，无法指向
        firstNode = new Node(null,null,null);
        //初始化尾节点,此时尾节点的前驱节点指向头节点,后继节点指向null
        lastNode = new Node(null,firstNode,null);
        //将头节点的后继节点指向尾节点
        firstNode.nextNode = lastNode;
    }

    //建立内部类Node用来表示每一个列表中的元素
    class Node{
        T data;        //节点的数据域
        Node prevNode; //节点的前驱指针域，指向前一个Node
        Node nextNode; //节点的后继指针域，指向后一个Node

        Node(T data, Node prevNode, Node nextNode){
            this.data = data;
            this.prevNode = prevNode;
            this.nextNode = nextNode;
        }
    };

    public int size(){
        return this.size;
    }
    public boolean isEmpty(){
        return size()==0;
    }
    //清空列表中的所有节点,将每个节点的数据域与指针域都指向null，来帮助GC工作
    public void clear(){
        for(Node n = firstNode; n != null;){
            Node next = n.nextNode;
            n.data =null;
            n.prevNode = null;
            n.nextNode = null;
            n = next;
        }
        firstNode = lastNode = null;
        this.size = 0;
    }

    public boolean add(T element){
        //新建一个节点，前驱节点指向尾节点的前一个节点，后继节点指向尾节点
        Node n = new Node (element,lastNode.prevNode,lastNode);
        //原先尾节点的前一个节点的后继节点指向我们新建的节点
        lastNode.prevNode.nextNode = n;
        //尾节点的前驱节点指向我们新建的节点
        lastNode.prevNode = n;
        this.size++;
        return true;
    }

    public void add(int index, T element){
        //一旦要插入元素的位置为负或大于目前的元素数量就抛出异常
        //此处允许index等于size，相当于在列表末尾插入元素
        if(index<0 || index>size())
            throw new IndexOutOfBoundsException();
        Node n;
        int i;
        //通过for循环，n将指向我们需要插入位置节点的前驱节点
        for(i=0,n = firstNode; i<index; i++){
            n = n.nextNode;
        }
        Node newNode = new Node(element, n , n.nextNode);
        //n节点的后继节点的前驱节点指向newNode
        n.nextNode.prevNode = newNode;
        //n节点的后继节点指向newNode
        n.nextNode = newNode;
        this.size++;
    }

    public boolean remove(T element){
        //如果删除的元素为null
        if(element == null){
            for(Node n = firstNode.nextNode; n.nextNode!=null;){
                if(n.data == null){
                    //将找到节点的前驱节点的后继结点指向该节点的后继节点
                    n.prevNode.nextNode = n.nextNode;
                    //将找到节点的后继结点的前驱节点指向该节点的前驱节点
                    n.nextNode.prevNode = n.prevNode;
                    //将该节点的指针域以及它本身都指向null，方便GC工作
                    n.prevNode = null;
                    n.nextNode = null;
                    n=null;
                    return true;
                }
                n = n.nextNode;
            }
            return false;
        }else{
            //如果删除的元素不为null
            for(Node n = firstNode.nextNode; n.nextNode!=null;){
                if(element.equals(n.data)){
                    //将找到节点的前驱节点的后继结点指向该节点的后继节点
                    n.prevNode.nextNode = n.nextNode;
                    //将找到节点的后继结点的前驱节点指向该节点的前驱节点
                    n.nextNode.prevNode = n.prevNode;
                    //将该节点的指针域以及它本身都指向null，方便GC工作
                    n.prevNode = null;
                    n.nextNode = null;
                    n = null;
                    this.size--;
                    return true;
                }
                n = n.nextNode;
            }
            return false;
        }
    }

    public void remove(int index){
        checkValidIndex(index);
        Node n = getNodeByValidIndex(index);
        //将找到节点的前驱节点的后继结点指向该节点的后继节点
        n.prevNode.nextNode = n.nextNode;
        //将找到节点的后继结点的前驱节点指向该节点的前驱节点
        n.nextNode.prevNode = n.prevNode;
        //将该节点的数据域、指针域以及它本身都指向null，方便GC工作
        n.data = null;
        n.nextNode = null;
        n.prevNode = null;
        n = null;
        this.size--;
    }

    public T get(int index){
        checkValidIndex(index);
        Node n = getNodeByValidIndex(index);
        return n.data;
    }
    public void set(int index, T element){
        checkValidIndex(index);
        Node n = getNodeByValidIndex(index);
        n.data = element;
    }
    public boolean contains(T element){
        if(element == null){
            for(Node n = firstNode.nextNode; n.nextNode!=null;){
                if(n.data == null){
                    return true;
                }
                n = n.nextNode;
            }
            return false;
        }else{
            //如果查找的元素不为null
            for(Node n = firstNode.nextNode; n.nextNode!=null;){
                if(element.equals(n.data)){
                    return true;
                }
                n = n.nextNode;
            }
            return false;
        }
    }
    private void checkValidIndex(int index){
        //一旦要插入元素的位置为负或大于目前的元素数量就抛出异常
        //此处不允许index等于size
        if(index<0 || index>=size())
            throw new IndexOutOfBoundsException();
    }
    //通过合法的index来获取当前的节点
    private Node getNodeByValidIndex(int index){
        Node n;
        int i;
        for(i=0,n=firstNode.nextNode;i<index;i++){
            n = n.nextNode;
        }
        return n;
    }
    public void printAll(){
        for(Node n=firstNode.nextNode;n.nextNode!=null;n = n.nextNode){
            if(n.data==null)
                System.out.println("null");
            else
                System.out.println(n.data.toString());
        }

    }

}
